/**
 * 给定一个字符串，每次操作可以交换两个位置，问将该字符串改造成
 * 反对称串的最少操作数量
 * 如果长度为奇数，显然不可能
 * 然后统计需要改变的对称位置一共有多少个，记作t
 * 再找到其中最多的一个字母所对应的数量m
 * 很明显如果最多的没有超过一半，则(t+1)/2必然可以调整好
 * 否则至少要m次
 */
#include <bits/stdc++.h>
using namespace std;

using llt = long long;

int N;
string S;

int proc(){
    if(N & 1) return -1;
    if(2 == N){
        if(S[0] == S[1]) return -1;
        return 0;
    }

    int cnt[256] = {0};
    for(auto c : S)if(++cnt[c]>N/2)return -1;

    map<char, int> yin;
    int total = 0;
    for(int i=0;i<N/2;++i){
        if(S[i] == S[N - 1 - i]){
            ++yin[S[i]];
            ++total;
        }
    }
    int mmax = 0;
    for(const auto & p : yin)mmax = max(mmax, p.second);

    if(mmax + mmax <= total){
        if(total & 1){
            return total / 2 + 1;
        }else{
            return total >> 1;
        }
    }

    return mmax;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int nofkase; cin >> nofkase;
    while(nofkase--){
        cin >> N >> S;
        cout << proc() << endl;
    }
    return 0;
}